public class Num4 {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

        if (m > n){
            // 交换位置
            int[] temps = nums1;
            nums1 = nums2;
            nums2 = temps;

            m = nums1.length;
            n = nums2.length;
        }

        int iMin = 0, iMax = m;
        while(iMin <= iMax){
            int i = (iMin + iMax)/2;
            int j = (m+n+1)/2-i;
            if (j != 0 && i != m && nums2[j-1] > nums1[i]){
                iMin = i + 1;
            } else if (i != 0 && j != n && nums2[j] < nums1[i-1]){
                iMax = i - 1;
            } else {

                // 找左侧最大值
                int maxLeft = 0;
                if (i == 0){
                    maxLeft = nums2[j-1];
                } else if(j == 0){
                    maxLeft = nums1[i-1];
                } else {
                    maxLeft = Math.max(nums1[i-1], nums2[j-1]);
                }
                if ((m+n)%2 == 1) return maxLeft;

                // 找右侧最小值
                int minRight;
                if (i == m){
                    minRight = nums2[j];
                } else if(j == n){
                    minRight = nums1[i];
                } else {
                    minRight = Math.min(nums1[i], nums2[j]);
                }

                return (maxLeft + minRight)/2.0;
            }
        }
        return 0;
    }
}
